#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


import heapq


class LinkedHead:
    def __init__(self, head, len=None):
        self.head = head
        if len:
            self.len = len
        else:
            self.len = self.len_linked_list(head)
        print(self.len)

    def len_linked_list(self, head):
        cnt = 0
        while head:
            cnt += 1
            head = head.next

        return cnt

    def __lt__(self, other):
        return self.len < other.len


class NodeWrap:
    def __init__(self, node):
        self.node = node

    def __lt__(self, other):
        return self.node.val < other.node.val


class Solution:
    '''
    用构建哈弗曼树的贪心算法顺序, 来进行多路归并排序
    '''
    def mergeKLists(self, lists):
        # return self.merge_k_lists_solution1(lists)
        return self.merge_k_lists_solution2(lists)

    def merge_k_lists_solution2(self, lists):
        heads = [NodeWrap(head) for head in lists if head is not None]
        if not heads:
            return None

        heapq.heapify(heads)

        dummy_head = tail = ListNode('dummy', None)

        while len(heads) > 1:
            top_node = heads[0].node
            tail.next = top_node
            tail = top_node

            if top_node.next:
                heapq.heapreplace(heads, NodeWrap(top_node.next))
            else:
                heapq.heappop(heads)

        tail.next = heads[0].node
        return dummy_head.next

    def merge_k_lists_solution1(self, lists):
        heads = [LinkedHead(head) for head in lists if head is not None]
        heapq.heapify(heads)

        if not heads:
            return None

        while len(heads) > 1:
            least_1 = heapq.heappop(heads)
            least_2 = heapq.heappop(heads)
            sum_len = least_1.len + least_2.len
            new_head = self.merge_sorted_list(least_1.head, least_2.head)
            heapq.heappush(heads, LinkedHead(new_head, sum_len))

        return heads[0].head

    def merge_sorted_list(self, h1, h2):
        # solutino 1
        dummy_head = tail = ListNode('dummy', None)

        while h1 and h2:
            if h1.val <= h2.val:
                # tail.next = h1
                # tail = h1
                move = h1
                h1 = h1.next
            else:
                move = h2
                h2 = h2.next
            tail.next = move
            tail = move
        remain = h1 or h2
        tail.next = remain

        return dummy_head.next


def show(n):
    while n:
        print("%s ----> " % n.val, sep=' ', end=' ')
        n = n.next
    print()


def main():
    print("start main")

    v5 = ListNode(11)
    v4 = ListNode(9, v5)
    v3 = ListNode(7, v4)
    v2 = ListNode(5, v3)
    v1 = ListNode(3, v2)
    v0 = ListNode(0, v1)

    v5 = ListNode(10)
    v4 = ListNode(8, v5)
    v3 = ListNode(6, v4)
    v2 = ListNode(4, v3)
    v1 = ListNode(2, v2)
    vm = ListNode(1, v1)

    s = Solution()
    ret = s.mergeKLists([v0, vm])
    show(ret)

if __name__ == "__main__":
    main()
